Subject: Loop prevention-Further details on one of my proposals.

From: Nagi Swaminathan <[email-masked]>
Date: Wed, 18 Aug 93 18:14:49 EDT

Choon Lee,

Thanks for the response. I suppose I did not make myself very clear.

The first proposal I suggested I think will work for both source routing and
non source routing network because it  uses  the data  link connection state
information which exists  within the DLSw to avoid looping rather than using
RIF fields or spanning tree. Let me try to elaborate.

Consider the following scenario:

                |--------|                      |--------|
  |-----|       |        |                      |        |      |--------|
  |     |       |  DLSw  |----------------------|  DLSw  |      |        |
  |     |-------|   A    |-------|              |   C    |------|        |
  |     |       |--------|       |              |--------|      |        |
  |     |                        |                              |        |
  |     |                        |                              |        |
  | LAN |                        |                              |        |
  |  1  |       |--------|       |              |--------|      |  LAN   |
  |     |       |        |       ---------------|        |      |   2    |
  |     |-------|  DLSw  |----------------------|  DLSw  |------|        |
  |     |       |    B   |                      |   D    |      |        |
  |     |       |--------|                      |--------|      |        |
  |     |                                                       |        |
  |     |                                                       |        |
  |     |                                                       |        |
  |     |       |--------|                      |--------|      |        |
  |     |-------|        |                      |        |      |        |
  |     |       | Bridge |----------------------| Bridge |------|        |
  ------        |   E    |                      |   F    |      |        |
                |--------|                      |--------|      ---------

Here the DLSws A,B,C and D and bridges(source routing or spanning tree) E
and F all exist in parallel.

The LLC connections have a property that they are uniquely identified by the
triplet source MAC address, destination MAC address and source SAP address.
(this scheme does not work if this not true).  As the broadcast frames pass
through the DLSws this information is left behind in each DLSw.  The
important point here is that unlike bridges which do not have any state
information regarding the LLC connections, the DLSw keep this information.
The DLSws can use this information to prevent loop formation both in source
routing and non source routing environments. It works as follows.

Each DLSw on receiving a broadcast frame/CANUREACH will look for existence
of LLC session with the same source MAC address, destination MAC address and
source SAP as indicated in the broadcast frame. If such a connection already
exists the broadcast frame is not forwarded and CANUREACH message is simply
ignored. Basically this prevents loop formation.

Consider the following scenarios(events listed in chronological order):
         
Note: The triplet within the brackets are source MAC address, destination
MAC address and source SAP.

        Scenario-I:

                A  receives  a  TEST(X,Y,04)  frame  and  sends a  CANUREACH
                message to C and D.

                B  receives  a  TEST(X,Y,04)  frame and  sends  a  CANUREACH
                message to D.

                Bridge E also forwards the TEST(X,Y,04) frame.

                C receives the CANUREACH message from A sends a TEST(X,Y,04)
                frame.

                D receives the CANUREACH message from A sends a TEST(X,Y,04) 
                frame. 

                D also receives a CANUREACH message from B and ignores it 
                because it already has an LLC connection with (X,Y,04).

                C receives two TEST(X,Y,04) frames(one from DLSw D and one 
                from the bridge F) and ignores them because it  
                already has an LLC connection with (X,Y,04).

                D receives two TEST(X,Y,04) frames(one from DLSw C and one 
                from bridge F) and ignores them  because it 
                already has an LLC connection with (X,Y,04).

                A receives two TEST(X,Y,04) frames(the TEST frames generated 
                by DLSW C and D and routed via the bridges) and ignores them
                because it already  has an LLC connection with (X,Y,04).

                B receives two TEST(X,Y,04) frames(the TEST frames generated 
                by DLSW C and D and routed via the bridges) and ignores them
                because it already  has an LLC connection with (X,Y,04).

                The station which sent the TEST frame receives 3 TEST 
                responses one each from DLSws A and B and one via bridge E.

        Scenario-II:

        This scenario considers the possibility of frames arriving at DLSws
        in an order that is different from scenario-I.  

                A receives a TEST(X,Y,04) frame and sends a CANUREACH message
                to C and D.

                Bridge E also forwards the TEST(X,Y,04) frame.

                C receives the TEST(X,Y,04) frame via the bridge and sends
                a CANUREACH message to A.

                D receives the TEST(X,Y,04) frame via the bridge and sends
                a CANUREACH message to A and B.

                C receives the CANUREACH message from A and ignores it 
                because it already has an LLC connection with (X,Y,04).

                D receives the CANUREACH from A and B and ignores it because 
                it already has an LLC connection with (X,Y,04).

                A receives the CANUREACH from C and D and ignores it because 
                it already has an LLC connection with (X,Y,04).

                B receives the CANUREACH from D and ignores it because 
                it already has an LLC connection with (X,Y,04).

                The station which sent the TEST frame receives 1 TEST 
                responses via bridge E.

If we can convince ourselves that this scheme does prevent loops(or may be I
am missing something), it will provide following advantages.

        . One scheme works for both source routing and non source routing
          environments.

        . Minimizes the broadcast frames in the network. 

        . Works for LLC connections passing through multiple DLSws(see note
          below).

Note:

Having one virtual ring number does  solve the looping problem in source 
routing environment. But, a connection may not be established if a path 
consists of more than a pair of DLSws. In the following figure a station on 
source routing network Y will not be able to connect to a station on source 
routing network Z as DLSw B will not forward the TEST frame sent by DLSw C 
as both DLSw B and DLSw C will have the same virtual ring number.

                ---------
                | SR    |
                | net   |
                |  Z    |
                |-------|
                    |
                    |
                |--------|                      |--------|
                |        |                      |        |
                |  DLSw  |----------------------|  DLSw  |
                |   A    |                      |   B    |
                |--------|                      |--------|
                                                    |
                                                    |
                                                    |
                                                |--------|
                                                |  SR    |
                                                |  net.  |
                                                |   X    |
                                                |--------|
                                                    |
                                                    |
                                                |--------|
                                                |        |
                                                |  DLSw  |
                                                |   C    |
                                                |--------|
                                                    |
                                                    |
                                                |--------|
                                                |        |
                                                |  SR    |
                                                |   net. |
                                                |   Y    |
                                                |--------|

        DLSw C in this case is probably used to avoid hop limitation. 
        The RFC does show an example of DLSw being employed in this fashion.

---

From: Choon Lee <[email-masked]>
Date: Wed, 18 Aug 1993 16:22:58 -0700

Nagi,

I have some comments on your proposal:

First of all, I wasn't clear on what you meant by connection. As I understand,
when a TEST frame (a LLC1 type connectionless frame), which becomes a CANUREACH
SSP frame across DLSw, flow between the two DLSw nodes, that does not constitute
a connection. A connection is established only after SABME/UA flow, and would
have 4-tuples (DA,SA,DSAP,SSAP).

But I see what you are saying now. If we keep the 3-tuple (DA,SA,SSAP) information
as they pass through the DLSw, that will generate 3 responses as you have described
in scenerio 1. That also means 2 ICANREACH messages (between A-C and between B-D).
Subsequently, it will result in 3 paths for each I frame between X and Y. No loop
but duplicate frames.

Further comments interspersed below.

>> Consider the following scenario:
Bridge F also receives 2 TEST frames and sends them across to LAN 1 and would
go through A-C again?

>> as both DLSw B and DLSw C will have the same virtual ring number.

I agree with you that connectivity between nets Z and Y is lost if the DLSw
are configured the same virtual ring number. In that scenerio, if DLSw B and C
are configured different VR, then it would work. However, this is what RFC1434
tries to avoid, because doing that can be dangerous and a loop can be formed 
(if Y and Z are the same net).

Your previous mail describe a method which I think can solve this particular problem. 
However, as you pointed out, it would require every DLSw node to know about
ALL VR that are configured in the entire network. Each time a new DLSw is added,
all other DLSw nodes have to be updated. I personally think that is hard to 
accept.

What do others think?

Regards,
Choon Lee
3Com Corp